/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-33-搜索旋转排序数组
 * @date 2025/5/23 15:19
 */
public class Solution33 {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // left的左边不可能是旋转位置,right右边也不可能是旋转位置
            int mid = (left + right) >>> 1;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 题目数据保证 nums 在预先未知的某个下标上进行了旋转,说明while跳出来一定是left == right
        assert left == right;
        if (nums[left] == target) {
            return left;
        }
        int ans1 = binarySearch(nums, 0, left - 1, target);
        if (ans1 != -1) {
            return ans1;
        }
        int ans2 = binarySearch(nums, right + 1, nums.length - 1, target);
        if (ans2 != -1) {
            return ans2;
        }
        return -1;
    }

    public int binarySearch(int[] nums, int left, int right, int target) {
        if (left < 0 || left >= nums.length || right < 0 || right >= nums.length) {
            return -1;
        }
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 没找到
        return -1;
    }
}
